package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-02 10:55
 **/
public class LeetCode2127 {

    public int maximumInvitations(int[] favorite) {
        int n = favorite.length;
        List<Integer>[] list = new List[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }

        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) {
            ++indeg[favorite[i]];
            list[i].add(favorite[i]);
        }

        //存放拓扑排序的结果
        Queue<Integer> q = new LinkedList<>();

        //使用dp数组更新终点的深度
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                q.add(i);
                dp[favorite[i]] = Math.max(dp[favorite[i]], dp[i] + 1);
            }
        }

        while (!q.isEmpty()) {
            int index = q.poll();
            for (int i : list[index]) {
                --indeg[i];
                if (indeg[i] == 0) {
                    q.add(i);
                    dp[favorite[i]] = Math.max(dp[favorite[i]], dp[i] + 1);
                }
            }
        }

        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            //可能存在多个环,将环中所有节点加入到temp集合中,环的入度为1
            if (indeg[i] == 1) {
                temp.add(i);
            }
        }

        //判断某个节点是否遍历过
        boolean[] visited = new boolean[n];
        //maxCircleLen保存的是最终结果
        int maxCircleLen = 0;
        //len2是所有2个节点的环及其树枝构成的长度
        int len2 = 0;
        for (int i : temp) {
            if (visited[i]) {
                continue;
            }

            visited[i] = true;
            int len = 0;
            int num = i;
            //该循环计算当前节点所在环的长度
            do {
                num = favorite[num];
                visited[num] = true;
                ++len;
            } while (num != i);

            //如果有新的2节点环,需要更新到len2中
            if (len == 2) {
                len2 = len2 + 2 + dp[i] + dp[favorite[i]];
            }

            //更新结果
            maxCircleLen = Math.max(maxCircleLen, len == 2 ? len2 : len);
        }

        return maxCircleLen;
    }

    public static void main(String[] args) {
        LeetCode2127 code = new LeetCode2127();
        //System.out.println(code.maximumInvitations(new int[]{1, 2, 3, 4, 5, 6, 3, 8, 9, 10, 11, 8}));
        System.out.println(code.maximumInvitations(new int[]{2,2,1,2}));
    }

}
